package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         17.16,
		Discription: "按摩师",
		Level:       1,
		Labels: map[string]int{
			"动态规划":  1,
			"有限状态机": 1,
		},
	})
}

func Massage(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	n := len(nums)
	rest := make([]int, n)
	work := make([]int, n)
	rest[0] = 0
	work[0] = nums[0]
	for i := 1; i < n; i++ {
		rest[i] = max(rest[i-1], work[i-1])
		work[i] = rest[i-1] + nums[i]
	}

	return max(work[n-1], rest[n-1])
}
